/**
 * Exercise 9.66
 * -----------------------------------------------------------------------------
 * Empirically compare binomial queues against heaps as the basis for sorting,
 * for randomly ordered keys with $N = 1000$, $10^4$, $10^5$, and $10^6$.
 * -----------------------------------------------------------------------------
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Item.h"
#include "PQ.h"

void PQsort(Item a[], int l, int r);

int main(int argc, char *argv[]){
    int narray[] = {1000, 10000, 100000, 1000000};
    int i;
    int size = sizeof(narray)/sizeof(int);
    for (i = 0; i < size; i++) {
        int N = narray[i];
        int j;
        int a[N];
        for (j = 0; j < N; j++) {
            a[j] = rand()%N;
        }
        clock_t start = clock();
        PQsort(a, 0, N-1);
        clock_t end = clock();

        printf("N = %d, Time = %.3f seconds\n", N, (double)(end - start) / CLOCKS_PER_SEC);
    }
    return 0;
}

/** 
 * Program 9.6 Sorting with a priority queue
 * -------------------------------------------
 * To sort a subarray `a[l..r]` using a priority-queue ADT,
 * we simply use `PQinsert` to put all the elements on the priority queue, and
 * then use `PQdelmax` to remove them, in decreasing order.
 * This sorting algorithm runs in time proportional to $N \lg N$, but
 * uses extra space proportional to the number of items to be sorted (for the priority queue).
 */
void PQsort(Item a[], int l, int r){
    PQinit(r-l+1);
    int k;

    for (k = l; k<=r; k++) {
        PQinsert(a[k]);
    }

    for (k = r; k >=l; k--) {
        a[k] = PQdelmax();
    }
}